package com.hjx.leetcode;

/**
 * 2、两数相加
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 *
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 *
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 *
 * 示例：
 *
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 执行用时 : 7 ms, 在所有 Java 提交中击败了63.73%的用户
 * 内存消耗 : 47.2 MB, 在所有 Java 提交中击败了72.62%的用户
 */
public class LeetCode_2 {


    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode dummyNode = new ListNode(0);
        //初始指向dummyNode
        ListNode curr = dummyNode;
        //进位
        int addOne = 0;
        while(l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + addOne;
            addOne = sum / 10;
            //新节点增加到curr后
            curr.next = new ListNode( sum % 10);
            //移动curr指向新增节点
            curr = curr.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;

        }
        return dummyNode.next;

    }

    /**
     * 第三版网上拷贝过来的 递归方式
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers3(ListNode l1, ListNode l2) {
        return doAddTwoNumbers(l1, l2, null);
    }

    public ListNode doAddTwoNumbers(ListNode l1, ListNode l2, ListNode prev) {
        ListNode next1 = null;
        ListNode next2 = null;
        int val1 = 0;
        int val2 = 0;
        if (l1 != null) {
            val1 = l1.val;
            next1 = l1.next;
        }
        if (l2 != null) {
            val2 = l2.val;
            next2 = l2.next;
        }
        ListNode newNode = new ListNode(val1 + val2);
        if (prev != null) {
            if (prev.val >= 10) {
                prev.val %= 10;
                newNode.val += 1;
            }
        }
        if (next1 != null || next2 != null || newNode.val >= 10) {
            newNode.next = doAddTwoNumbers(next1, next2, newNode);
        }
        return newNode;
    }

    /**
     * 我的第二版
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode listNode = null;
        ListNode temp = null;
        int jinwei = 0;
        while(l1 != null || l2 != null){
            int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + jinwei;

            if (listNode == null) {
                listNode = new ListNode(sum % 10);
                temp = listNode;
            } else {
                //为下一位赋值
                temp.next = new ListNode(sum % 10);
                //切换引用
                temp = temp.next;
            }

            //切换引用
            l1 = l1 == null ? l1 : l1.next;
            l2 = l2 == null ? l2 : l2.next;
            //计算进位
            jinwei = sum / 10;

        }
        if (jinwei > 0) {
            temp.next = new ListNode(jinwei);
        }
        return listNode;
    }

    /**
     * 我的第一版
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {

        int l1Len = getLength(l1);
        int l2Len = getLength(l2);
        int jinwei = 0;
        ListNode result = null;
        ListNode temp = null;
        if (l1Len > l2Len){

            for (int i = 0; i < l1Len; i++) {
                if (i <= l2Len - 1){
                    int sum = l1.val + l2.val + jinwei;
                    //当前位数取余

                    if (temp == null) {
                        result = new ListNode(sum % 10);
                        temp = result;
                    } else {
                        temp.next = new ListNode(sum % 10);
                        temp = temp.next;
                    }
                    //进位取整
                    jinwei = sum / 10;
                    //移动指针
                    l1 = l1.next;
                    l2 = l2.next;
                } else {
                    int sum = l1.val + jinwei;
                    temp.next = new ListNode(sum % 10);
                    temp = temp.next;
                    jinwei = sum / 10;
                    l1 = l1.next;
                }


            }

        } else if(l2Len > l1Len){

            for (int i = 0; i < l2Len; i++) {
                if (i <= l1Len - 1){
                    int sum = l1.val + l2.val + jinwei;
                    //当前位数取余

                    if (temp == null) {
                        result = new ListNode(sum % 10);
                        temp = result;
                    } else {
                        temp.next = new ListNode(sum % 10);
                        temp = temp.next;
                    }
                    //进位取整
                    jinwei = sum / 10;
                    //移动指针
                    l1 = l1.next;
                    l2 = l2.next;
                } else {
                    int sum = l2.val + jinwei;
                    temp.next = new ListNode(sum % 10);
                    temp = temp.next;
                    jinwei = sum / 10;
                    l2 = l2.next;
                }


            }

        } else {

            result = getListNode(l1, l2, l1Len, jinwei, result, temp);
        }
        if (jinwei > 0){
            temp.next = new ListNode(jinwei);
        }

        return result;
    }

    private ListNode getListNode(ListNode l1, ListNode l2, int l1Len, int jinwei, ListNode result, ListNode temp) {
        for (int i = 0; i < l1Len; i++) {

            int sum = l1.val + l2.val + jinwei;
            //当前位数取余

            if (temp == null) {
                result = new ListNode(sum % 10);
                temp = result;
            } else {
                temp.next = new ListNode(sum % 10);
                temp = temp.next;
            }
            //进位取整
            jinwei = sum / 10;
            //移动指针
            l1 = l1.next;
            l2 = l2.next;

        }
        if (jinwei > 0){
            temp.next = new ListNode(jinwei);
        }
        return result;
    }


    public int getLength(ListNode listNode){
        int length = 0;
        while (listNode != null){
            length++;
            listNode = listNode.next;
        }
        return length;
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}
